//用队列实现栈
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <Stdbool.h>
typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}QueueNode;


typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

//销毁
void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

//插入尾
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->next = NULL;
	newnode->val = x;
	if (pq->head == NULL)
	{
		pq->head = newnode;
		pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

//删除头
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head!=NULL);
	QueueNode* cur = pq->head;
	pq->head = pq->head->next;
	free(cur);
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}

}

//查看头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	return pq->head->val;
}

//查看尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	return pq->tail->val;
}
//查看队列数据个数
int QueueSize(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	int num = 0;
	while (cur)
	{
		num++;
		cur = cur->next;
	}
	return num;
}


//查看队列是否为空 为空返回1 非空返回0
int QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL ? 1 : 0;
}





typedef struct 
{
 Queue _q1;
 Queue _q2;   
} MyStack;


MyStack* myStackCreate() {
    MyStack* st=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->_q1);
    QueueInit(&st->_q2);
    return st;
}

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->_q1))
        QueuePush(&obj->_q1,x);
    else
        QueuePush(&obj->_q2,x);

}

int myStackPop(MyStack* obj) {
    Queue* empty =&obj->_q1;
    Queue* nonempty =&obj->_q2;
    if(!QueueEmpty(&obj->_q1))
    {
        empty =&obj->_q2;
        nonempty =&obj->_q1;
    }
    while(QueueSize(nonempty)>1)
    {
        QueuePush(empty,QueueFront(nonempty));
        QueuePop(nonempty);
    }
    int ret =QueueFront(nonempty);
    QueuePop(nonempty);
    return ret;

}

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->_q1))
    {
        return QueueBack(&obj->_q1);
    }
    else
    {
        return QueueBack(&obj->_q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->_q1)&&QueueEmpty(&obj->_q2);
}

void myStackFree(MyStack* obj) {
    
}